import java.util.*;

/**
* @description: leetCode 周赛303 t4
* @author hewei
* @date 2022/7/24 15:10
* @version 1.0
*/

public class CountExcellentPairs {

    public long countExcellentPairs1(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) continue;
            int temp = nums[i];
            set.add(temp);
            list.add(Integer.bitCount(temp));
        }
        Collections.sort(list);
        long ans = 0;
        for (int i = 0; i < list.size(); i++) {
            int l = i;
            int r = nums.length - 1;
            int temp = list.get(i);
            while (l < r) {
                int mid = (r - l) / 2 + l;
                if (list.get(mid) + temp >= k) {
                    r = mid;
                } else l = mid + 1;
            }
            if (list.get(l) + temp >= k) {
                ans += (list.size() - l) * 2;
                ans -= l == i ? 1 : 0;
            }
        }
        return ans;
    }

    public long countExcellentPairs(int[] nums, int k) {
        HashSet<Integer> set = new HashSet<>();
        int[] count = new int[32];
        for (int num : nums) {
            if (set.contains(num)) continue;
            set.add(num);
            count[Integer.bitCount(num)]++;
        }
        long ans = 0;
        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < 32; j++) {
                if (i + j >= k) ans += count[i] * count[j];
            }
        }
        return ans;
    }
}
